/**
 * 构造二叉树
 */
class TreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 *         1
 *        /  \
 *      2     3
 *    /      /  \
 *   6      4    5
 */
let arr = [1, 2, 3, 6, null, 4, 5];
let LN = 0;

// 根据数组创建一棵二叉树，也就是前序遍历构造二叉树
function createTree(arr, i) {
    if (i >= arr.length || !arr[i]) return null;
    let tree = new TreeNode(arr[i]);
    tree.left = createTree(arr, 2 * i + 1);
    tree.right = createTree(arr, 2 * i + 2);
    return tree;
}

let tree = createTree(arr, 0);
// console.dir(JSON.stringify(tree, null, 4));

/**
 * 前序遍历
 * @param {*} root 
 */
function startDFS(root) {
    // // 递归
    // if (!root) return [];
    // let arr = [root.val, ...startDFS(root.left), ...startDFS(root.right)];
    // return arr;
    // 非递归,也就是迭代
    // 采用了栈存储思维
    // if (!root) return [];
    // let stack = [root]; // 定义一个栈
    // let outarr = []; // 定义一个输出数组
    // while (stack.length) { // 循环条件stack不为空
    //     let top = stack.pop(); // 实时获取栈顶的数据
    //     outarr.push(top.val);
    //     if (top.right) { // 右子树先压栈
    //         stack.push(top.right);
    //     }
    //     if (top.left) { // 左子树压栈之后等到pop时就是最先出栈
    //         stack.push(top.left);
    //     }
    // }
    // 另一种写法
    if (!root) return [];
    let stack = []; // 定义一个栈
    let outarr = []; // 定义一个输出数组
    while (stack.length || root) { // 循环条件stack不为空
        // outarr.push(root.val);
        while (root) {
            stack.push(root);
            outarr.push(root.val);
            root = root.left;
        }
        root = stack.pop();
        root = root.right;
    }
    return outarr;
}

/**
 * 中序遍历
 * @param {*} root 
 */
function midDFS(root) {
    // 递归
    // if (!root) return [];
    // let arr = [...midDFS(root.left), root.val, ...midDFS(root.right)];
    // return arr;

    // 迭代
    if (!root) return [];
    let stack = []; // 定义一个栈
    let outarr = []; // 定义一个输出数组
    while (root || stack.length) { // 循环条件stack不为空
        while (root) { // 每遇到左子树先全部入栈
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        outarr.push(root.val);
        root = root.right;
    }
    return outarr;
}

/**
 * 后序遍历
 * @param {*} root 
 */
function endDFS(root) {
    // // 递归
    // if (!root) return [];
    // let arr = [...endDFS(root.left), ...endDFS(root.right),root.val];
    // return arr;

    // // 迭代，先右子树进栈，然后用unshift插队即可
    // if (!root) return [];
    // let stack = []; // 定义一个栈
    // let outarr = []; // 定义一个输出数组
    // // let top = root;
    // while (root || stack.length) { // 循环条件stack不为空
    //     while (root) { // 每遇到左子树先全部入栈
    //         stack.push(root);
    //         outarr.unshift(root.val); // unshift是在数组前面插入新的数据,shift是将数组第一个数据删除并且返回被删除的数据
    //         root = root.right;
    //     }
    //     root = stack.pop();
    //     root = root.left;
    // }
    // 使用标记法
    let stack = [];
    let visited = null; // 标记右子树是否被访问过
    let cur = root;
    let outarr = [];
    // 把所有左子树入栈
    while (cur) {
        stack.push(cur);
        cur = cur.left;
    }
    while (stack.length) {
        let top = stack.pop();
        // 右子树为空或者已经被访问过
        if (top.right === null || top.right === visited) { // top.right当top为父节点的时候
            out.push(top.val);
            visited = top;
        } else {
            cur = top.right;
            while (cur) {
                stack.push(cur);
                cur = cur.left;
            }
        }
    }
    return outarr;
}

// 层次遍历，
// 巧妙使用队列思想
function levelDFS(root) {
    let queue = [root];
    let ret = [];
    while (queue.length) {
        let tmp = [];
        let ln = queue.length;
        for (let i = 0; i < ln; i++) {
            let ql = queue.shift();
            tmp.push(ql.val);
            if (ql.left) {
                queue.push(ql.left);
            }
            if (ql.right) {
                queue.push(ql.right);
            }
        }
        ret.push(tmp);
    }
    return ret;
}

// function equelTree(tree1,tree2) {
//     if ()
// }



console.log(startDFS(tree));
console.log(midDFS(tree));
console.log(endDFS(tree));
console.log(levelDFS(tree));
